package com.fengye.algorithms.huawei.dp;

import java.util.Scanner;

/**
 * https://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507?tpId=37&tqId=21308&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=
 * @Author fengye
 * @Date 2023/3/2 14:55
 **/
public class LongestPalindromeMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.next();
            System.out.println(longestPalindrome2(str));
        }
    }

    private static String longestPalindrome2(String s) {
        String result = "";
        boolean[][] dp = new boolean[s.length()][s.length()];
        char c[] = s.toCharArray();

        for(int i=0;i<c.length;i++) {
            for(int j=i;j>=0;j--) {
                // 单个字符
                if(i-j<2 && c[i]==c[j]){
                    dp[j][i] = true;
                } else if(c[i] == c[j] && dp[j+1][i-1]) {
                    dp[j][i] = true;
                }
                if(dp[j][i] && i-j+1 > result.length()) {
                    result = s.substring(j,i+1);
                }
            }
        }
        return result;
    }


    static int start = 0, end = 0;
    public static String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;
        char[] c = s.toCharArray();
        longestPallindromeAt(c, 0);
        return s.substring(start, end + 1);
    }
    private static void longestPallindromeAt(char[] c, int p) {
        int a = p;
        int b = p;
        int n = c.length;
        if ((p == n - 1 || (n - p) < (end - start + 1)/2)) {
            return;
        }

        while (b < n - 1 && c[b] == c[b + 1]) {
            b++;
        }

        p = b;
        while (a > 0 && b < n - 1 && c[a - 1] == c[b + 1]){
            a--;
            b++;
        }
        if ((b - a) > (end - start)){
            end = b;
            start = a;
        }
        longestPallindromeAt(c, p + 1);
    }
}
